package leetcode

import kotlinetc.println

//https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
/**
Suppose an sort.getArray sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the sort.getArray return true, otherwise return false.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:

Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Follow up:

This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
Would this affect the run-time complexity? How and why?
 */
fun main(args: Array<String>) {

    //1,3,1,1,1
    //2,5,6,0,0,1,2   3
    //2,2,2,0,1   0
    searchII(intArrayOf(2,2,2,0,1 ), 0).println()
}

/**
 * similar [search] 唯一不同的是 现在会出现重复数字，会 在判断哪半边是连续的时候 造成影响，那么现在必须在一段区间内去重 后再判断
 */
fun searchII(nums: IntArray, target: Int): Boolean {


    var l = 0
    var r = nums.lastIndex
    var mid: Int
    while (l <= r) {
        mid = (l + r + 1) / 2

        if (target == nums[mid]) return true

        if (nums[r] > nums[l] && target !in nums[l]..nums[r]) break  //not found

        var left = l
        var middle = mid
        var right = r
        //左边 去重
        while (left < middle && nums[left] == nums[left + 1]) left++
        while (left < middle && nums[middle] == nums[middle - 1]) middle--


        if (nums[middle] > nums[left]) { //左边连续
            if (target in nums[left]..nums[middle]) r = middle - 1
            else l = middle + 1
        } else { //右边连续，但是无法确定是升序还是降序

            middle = mid

            //右边去重
            while (middle < r && nums[middle] == nums[middle + 1]) middle++
            while (r > middle && nums[r] == nums[r - 1]) r--

            //这里需要特别判断  1，3，1 这种情况，因为会打破数组升序的特点
            if (nums[middle] == nums[r] && r > middle) r--

            if (target in nums[middle]..nums[r])
                l = middle + 1
            else r = mid - 1

        }

    }

    return false
}
